Optymalizacja dysku

Limit pamięci: 32 MB

Dysk składa się z sektorów ponumerowanych kolejno od do . Dowolny niepusty ciąg sektorów o kolejnych numerach nazywamy blokiem. Długość bloku to liczba zawartych w nim sektorów. Bloki są rozłączne, jeśli nie mają wspólnego sektora.

Na dysku są zapisane pliki. Jeden plik może być zapisany w wielu sektorach, które nie muszą tworzyć jednego bloku. Aby prawidłowo odtworzyć plik trzeba odczytać te sektory we właściwej kolejności. Ten ciąg sektorów wyznacza ciąg rozłącznych bloków, z których każdy zawiera jeden lub więcej sektorów. Sektory wewnątrz każdego bloku czyta się według kolejności numerów.

Opis rozmieszczenia pliku na dysku jest ciągiem par liczb całkowitych dodatnich. Każda taka para składa się z numeru początkowego sektora bloku oraz długości tego bloku.

Przykład

Ciąg par:

7 3
2 1
5 2

Każdy sektor na dysku może być wolny albo jest w nim zapisana część tylko jednego pliku (lub jeden cały plik).

Każdy plik ma unikalny identyfikator - dodatnią liczbę całkowitą z zakresu od do , gdzie jest liczbą plików na dysku.

Dysk jest zoptymalizowany, gdy:

• każdy plik jest pamiętany w jednym bloku (w kolejnych sektorach),
• plik o mniejszym identyfikatorze zajmuje sektory o niższych numerach, niż każdy plik o wyższym identyfikatorze,
• każdy sektor wolny ma numer większy niż każdy sektor zajęty.

Na dysku można wykonywać następujące operacje:

• kopiowanie zawartości bloku do rozłącznego z nim bloku o tej samej długości,
• zamiana zawartości dwóch rozłącznych bloków o tej samej długości.

Kopiowanie bloku o długości trwa mikrosekund.

Zamiana zawartości dwóch bloków o długości trwa mikrosekund.

Polecenie kopiowania pliku ma postać:

K początek_bloku nowy_początek_bloku długość_bloku

Polecenie zamiany ma postać:

Z początek_bloku1 początek_bloku2 długość_bloku

Zadanie

Ułóż program, który:

• wczytuje liczbę sektorów i liczbę plików oraz opisy ich rozmieszczeń na dysku ze standardowego wejścia,
• sprawdza, czy dysk jest zoptymalizowany. Jeśli tak, to zapisuje w standardowym wyjściu tylko jeden wyraz NIC. Jeśli nie, to generuje odpowiedni ciąg poleceń powodujących optymalizację dysku w taki sposób, aby czas optymalizacji był jak najkrótszy (nie jest istotna liczba poleceń, tylko łączny czas ich wykonania), po czym zapisuje ten ciąg poleceń w standardowym wyjściu.

Wejście

W pierwszym wierszu standardowego wejścia są zapisane dwie liczby całkowite dodatnie: liczba sektorów na dysku , nie większa niż , oraz liczba plików . Dalej w kolejnych wierszach następują opisy rozmieszczenia plików na dysku. Każdy opis pliku zawiera w pierwszym wierszu dwie liczby: identyfikator pliku z zakresu od do oraz dodatnią liczbę rozłącznych bloków, w których zapisany jest ten plik. W następnych wierszach znajduje się opis rozmieszczenia pliku w postaci odpowiedniego ciągu par liczb całkowitych dodatnich, każda para w osobnym wierszu. Liczby w wierszach są oddzielone pojedynczymi odstępami. Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego sprawdzać.

Wyjście

Standardowe wyjście ma zawierać tylko jeden wyraz NIC, gdy dysk jest już zoptymalizowany, albo ciąg poleceń, każde w osobnym wierszu. Każde polecenie musi być zapisane zgodnie z podanym poniżej formatem: najpierw duża litera K albo Z, pojedynczy odstęp, potem trzy liczby całkowite dodatnie oddzielane pojedynczymi odstępami.

Przykład

Dla danych wejściowych:

200 2 
2 2
51 10
41 10
1 2
71 20
11 20 

poprawną odpowiedzią jest:

K 21 31 10 
K 11 21 10
K 71 1 20
Z 41 51 10

Autorzy zadania: Tomasz Śmigielski, Piotr Krysiuk.